package org.example.chap01;

/**
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，
 * 使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 */
public class maxArea {

    public static void main(String[] args) {

        int[] nums={1,8,6,2,5,4,8,3,7};
//        int result = solution1(nums);
        int result = solution2(nums);
        System.out.println("最大面积是:"+result);

    }

    /**
     * 这个算法的时间复杂度是 O(n^2)
     * @param a
     * @return
     */
    public static int solution1(int[] a){
        int max=0;
        for(int i = 0; i < a.length-1; i++) {
            for (int j = i+1; j < a.length; j++) {
                int area = (j-i)*Math.min(a[i],a[j]);
                max = Math.max(max,area);
            }
        }
        return max;
    }

    /**
     * 算法2,时间复杂度 O(n)
     * @return
     */
    public static int solution2(int[] height){

        int max = 0;
        for (int i = 0,j = height.length-1; i<j; ) {
            int minHeight = height[i]<height[j]?height[i++]:height[j--];
            int area = (j-i+1) * minHeight;
            max = Math.max(max,area);
        }
        return max;

    }
}
